#include <vector>
using namespace std;
#include <climits>
#include <ctime>
#include <cstdlib>


//version 1  使用堆  时间复杂度不合格！！！
class Solution {
public:
    void AdjustDown(vector<int>& heap, int parent, int heapsize){
        while(parent * 2 + 1 < heapsize){
            //进来就一定有左孩子 -> 左右孩子中更小的那一个！
            int child = parent * 2 + 1;
            if(child + 1 < heapsize && heap[child] > heap[child + 1]) child += 1;

            //得到了左右孩子中更小的那个
            if(heap[parent] > heap[child]) {
                std::swap(heap[parent], heap[child]);
                parent = child;
            }
            else break;
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(k, INT_MIN); //小堆
        for(auto& x : nums){
            if(x > heap[0]){
                heap[0] = x;
                AdjustDown(heap, 0, k);
            }
        }
        return heap[0];
    }
};



//version 2
class Solution {
private:
    int qsortAndFindKthLargest(vector<int>& nums, int l, int r, int k){
        if(l == r) return nums[l];
        int key = nums[(rand() % (r - l + 1)) + l];
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(nums[i] < key) std::swap(nums[++left], nums[i++]);
            else if(nums[i] == key) ++i;
            else std::swap(nums[--right], nums[i]);
        }
        //[l, left] [left + 1, right - 1] [right, r]
        if(r - right + 1 >= k) return qsortAndFindKthLargest(nums, right, r, k);
        else if(r - left >= k) return nums[left + 1];
        else return qsortAndFindKthLargest(nums, l, left, k - (r - left));
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned int)time(nullptr));
        int ret = qsortAndFindKthLargest(nums, 0, nums.size() - 1, k);
        return ret;
    }
};